package com.future;

/**
 * Description: BM12 单链表的排序
 *
 * @author weiruibai.vendor
 * Date: 2022/8/1 09:58
 */
public class Solution_BM12 {

    public static void main(String[] args) {
        Solution_BM12 bm12 = new Solution_BM12();
        // {1,3,2,4,5}
        ListNode head = new ListNode(1);
        head.next = new ListNode(-3);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(0);
        head.next.next.next.next.next.next = new ListNode(90);
        head.next.next.next.next.next.next.next = new ListNode(9);
        ListNode node = bm12.sortInList(head);
        print(node);
    }

    /**
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode left = head;
        ListNode right = head.next;
        /**
         * 找到中点
         */
        while (right != null && right.next != null) {
            left = left.next;
            right = right.next.next;
        }
        right = left.next;
        left.next = null;
        left = head;
        /**
         * 左边排好序
         */
        ListNode leftSort = sortInList(left);
        /**
         * 右边排好序
         */
        ListNode rightSort = sortInList(right);
        /**
         * 合并左边和右边
         */
        return process(leftSort, rightSort);
    }

    private ListNode process(ListNode left, ListNode right) {
        if (left == null && right == null) {
            return null;
        }
        ListNode newHead = new ListNode(-1);
        ListNode opHead = newHead;
        while (left != null && right != null) {
            ListNode next;
            if (left.val <= right.val) {
                next = left;
                left = left.next;
            } else {
                next = right;
                right = right.next;
            }
            opHead.next = next;
            opHead = opHead.next;
        }
        if (left != null) {
            opHead.next = left;
        }
        if (right != null) {
            opHead.next = right;
        }
        return newHead.next;
    }

    private static void print(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

}
